package hot100;

import java.util.HashMap;
import java.util.Map;

public class IsPalindrome {
    public class ListNode {
        int val;
        ListNode next;

        ListNode(int x) {
            val = x;
            next = null;
        }
    }

    public boolean isPalindrome(ListNode head) {
        //定义前驱节点的map
        Map<ListNode,ListNode> pre = new HashMap<>();
        //初始化每个节点的前驱节点
        ListNode p = head;
        while (p.next != null) {
            pre.put(p.next,p);
            p = p.next;
        }
        ListNode tail = p;//尾节点
        ListNode left = head;
        ListNode right = tail;
        while (left != null && right != null && left != right && right.next != left) {
            if (left.val != right.val) return false;
            left = left.next;
            right = pre.get(right);
        }

        return true;
    }
}
